package acwing;

/**
 * 1. 问题描述
 *      输入两个整数n和m，输出一个n行m列的矩阵，将数字 1 到 n*m 按照回字蛇形填充至矩阵中。
 *
 * 2. 算法分析
 *      主要使用的技巧为：偏移数组，可以简化我们的代码，在一些搜索算法的中都可以使用这种技巧来简化我们的代码
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q003_蛇形矩阵 {
    public static void main(String[] args) {

    }

    /**
     * 打印出n*m的蛇形矩阵
     * 1 2 3
     * 8 9 4
     * 7 6 5
     * @param n
     * @param m
     */
    public static void snakeMatrix(int n,int m) {
        int[][] mat = new int[n][m];
        int[] dx = {-1,0,1,0}; // x方向的偏移数组
        int[] dy = {0,1,0,-1}; // y方向的偏移数组
        int x = 0; int y = 0; // 定义初始位置
        int d = 1; // 定义初始方向
        for(int i = 1; i <= n * m; i++) {
            mat[x][y] = i; // 将当前位置填充上元素
            int a = x + dx[d]; // 记录下一次的位置(当前方向的偏移之后x的坐标)
            int b = y + dy[d]; // 同上，只不过为y的方向
            // 判断当前偏移之后的位置是否满足索引条件
            if(a < 0 || a >= n || b < 0 || b >= m || mat[a][b] != 0) {
                d = (d + 1) % 4; // 简单的周期性规律
                a = x + dx[d];
                b = y + dy[d];
            }
            x = a;
            y = b;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(mat[i][j]+" ");
            }
            System.out.println();
        }
    }
}
